package algorithm_learn.sort;

public class Code_insertSort {
    public static void main(String[] args) {
        int[] arr = {5,1,5,1,3,4,1,4,1,2,4,1};
        printArr(arr);
        insertSort1(arr);
        //排序后
        printArr(arr);
    }
    public static void printArr(int[] arr){
        for (int i = 0;i<arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
    //插入排序
    public static void insertSort1(int[] arr){
        //边界
        if(arr == null|| arr.length < 2){
            return;
        }
        int N = arr.length;
        //0-0 ok
        //0-1
        //0-2
        //0-n-1
        //新来的数在end位置
        for (int end = 1;end<N;end++){
            int newNumIndex = end;
            while (newNumIndex - 1>= 0 && arr[newNumIndex-1]>arr[newNumIndex]){
                swap(arr,newNumIndex-1,newNumIndex);
                //往左移动
                newNumIndex --;
            }
        }
    }
    public static void insertSort2(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
        int N = arr.length;
        for(int end = 1;end<N;end++){
           for(int pre = end - 1;pre >= 0 && arr[pre]>arr[pre+1];pre--){
               swap(arr,pre,pre+1);
           }
        }
    }
    public static void swap(int[] arr,int i,int j){
        System.out.println("交换状态："+arr[i]+"<=====>"+arr[j]);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        printArr(arr);
    }
}
